/*
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#pragma once

#include "NTree.h"
#include "stdio.h"
#include <algorithm>
#include "Constructors.h"
#include "ThickenConstructors.h"
#include "Relations.h"
#include <list>
#include "NTreeHelpers.h"
#include <unordered_map>

/*
 * user data policy
 * 	- oper1 overwrites oper2
 * 	- oper2 overwrites oper1 only if oper1 has 'Nil' and oper2 is 'Solid'
 */


class Operators
{
public:
	template<class Oper, class V, class T1, class T2, class T3>
	static void
	booleanOpNodes(typename NTree<V, T1>::Node& res, const typename NTree<V, T1>::Node& n1,
			const typename NTree<V, T2>::Node& n2)
	{
		const VoxelType type1= n1.getType();
		const VoxelType type2= n2.getType();

		if(type1==Both && type2==Both)
		{
			if(res.getType() != Both)
				res.createSubNodes();
			for (unsigned int i = 0; i < V::childCount; i++)
				booleanOpNodes<Oper, V, T1, T2, T3>(res.getSubNode(i), n1.constGetSubNode(i), n2.constGetSubNode(i));
			res.simplify(false);
			return;
		}
		if(type1==Both)
		{
			if(res.getType() != Both)
				res.createSubNodes();
			for (unsigned int i = 0; i < V::childCount; i++)
				booleanOpNodes<Oper, V, T1, T2, T3>(res.getSubNode(i), n1.constGetSubNode(i), n2);
			res.simplify(false);
			return;
		}
		if(type2==Both)
		{
			if(res.getType() != Both)
				res.createSubNodes();
			for (unsigned int i = 0; i < V::childCount; i++)
				booleanOpNodes<Oper, V, T1, T2, T3>(res.getSubNode(i), n1, n2.constGetSubNode(i));
			res.simplify(false);
			return;
		}
		//two leafs
		Oper::op(res, n1, n2);
	}

	//will raise given trees to same level
	template<class Oper, class V, class T1, class T2, class T3>
	static void
	booleanOp(NTree<V, T3> &outTree, NTree<V, T1>& t1, NTree<V, T2>& t2)
	{
		int iCommonLevel=std::max(t1.getSize(), t2.getSize());
		t1.raise(iCommonLevel);
		t2.raise(iCommonLevel);
		outTree.raise(iCommonLevel);
		for (unsigned int i = 0; i < V::childCount; i++)
			booleanOpNodes<Oper, V, T1, T2, T3>(outTree.getRoot(i), t1.constGetRoot(i), t2.constGetRoot(i));
		outTree.lower();
	}

	template<class V, class T>
	class OpUnion
	{
	public:
		static void
		op(typename NTree<V, T>::Node& res, const typename NTree<V, T>::Node& n1, const typename NTree<V, T>::Node& n2)
		{
			if(n1.getType()==Solid)
				res=n1;
			else if(n2.getType()==Solid)
				res=n2;
			else res = n1;
		}
	};

	template<class V, class T>
	class OpDifference
	{
	public:
		static void
		op(typename NTree<V, T>::Node& res, const typename NTree<V, T>::Node& n1, const typename NTree<V, T>::Node& n2)
		{
			if(n2.getType()==Solid)
			{
				res=typename NTree<V, T>::Node(Nil);
				return;
			}
			//else it is n1
			res=n1;
		}
	};

	template<class V, class T>
	class OpIntersection
	{
	public:
		static void
		op(typename NTree<V, T>::Node& res, const typename NTree<V, T>::Node& n1, const typename NTree<V, T>::Node& n2)
		{
			//if one is nil, don't generate
			if(n1.getType()==Nil)
			{
				res=n1;
				return;
			}
			if(n2.getType()==Nil)
			{
				res=n2;
				return;
			}
			//both must be solid
			res=n1;
		}
	};

	template<class VecType, class DataType>
	static void
	surfelsNodes(typename NTree<VecType, DataType>::Node& res,
			const typename NTree<VecType, DataType>::Node& node,
			const Area<VecType> &area,
			const NTree<VecType, DataType>& tree,
			std::unordered_map<VecType, unsigned int>& leafCache)
	{
		if(node.getType()==Nil)
			return;

		static const int nNeighbors = VecType::neighborCount;
		static const int nChecks = nNeighbors -1;

		if(area.expo)
		{//recurse
			VecType neighbors[nChecks];
			neighbors[0]=area.pos;
			area.pos.neighbors(neighbors);
			int nSolid=0;
			for (int i=0; i < nChecks; i++)
			{
				if(tree.queryAreaType(Area<VecType>(area.expo, neighbors[i]))==Solid)
					nSolid++;
				else
					break;
			}

			if(nSolid==nChecks)
				return;
			//printf("Area %d %s\n{\n", area.expo, area.pos.toString().c_str());

			Area<VecType> subAreas[VecType::childCount];
			area.subAreas(subAreas);
			res=typename NTree<VecType, DataType>::Node(Both);
			for (unsigned int i = 0; i < VecType::childCount; i++)
				surfelsNodes(res.getSubNode(i), node.getType()==Both ? node.constGetSubNode(i) : node, subAreas[i], tree, leafCache);
			return;
			//printf("}\n");
		}
		//level 0
		VecType neighbors[nNeighbors];
		area.pos.neighbors(neighbors);
		for(int i=0; i < nNeighbors; i++)
		{
			//look up in cache
			VecType halfNeighbor=neighbors[i].half();
			VecType vDiff=neighbors[i]-halfNeighbor.doubleVec();
			unsigned int uiNeighborIndex=(vDiff.x<<2) | (vDiff.y<<1) | vDiff.z;
			//look up in cache
			if(leafCache.find(halfNeighbor)==leafCache.end())
			{
				const typename NTree<VecType, DataType>::Node* pNode=
						tree.queryArea(Area<VecType>(1, halfNeighbor));

				if(pNode==nullptr)
					leafCache[halfNeighbor]=0;
				else
				{
					switch(pNode->getType())
					{
					case Nil:
						leafCache[halfNeighbor]=0;
						break;
					case Solid:
						leafCache[halfNeighbor]=-1;
						break;
					default:
						unsigned int uiBitMask=0;
						for(unsigned int i=0; i<VecType::childCount; i++)
							if(pNode->constGetSubNode(i).getType()!=Nil)
								uiBitMask |= 1<<i;
						leafCache[halfNeighbor]=uiBitMask;
						break;
					}
				}
			}
			unsigned int leafState=leafCache[halfNeighbor]&(1<<uiNeighborIndex);
			if(!leafState)//is Nil
			{
				//printf("Pos: %s\n", area.pos.toString().c_str());
				assert(node.getType()==Solid);
				res=typename NTree<VecType, DataType>::Node(node.getData());
				return;
			}
		}
	}

	template<class VecType, class DataType>
	static void
	surfels(NTree<VecType, DataType> &outTree, const NTree<VecType, DataType>& tree)
	{
		outTree=NTree<VecType, DataType>(tree.getSize());
		Area<VecType> subs[VecType::childCount];
		tree.subAreas(subs);

		//caches all level 0 nodes with coordinate of level 1 nodes
		std::unordered_map<VecType, unsigned int> leafCache;

		for(unsigned int i=0; i<VecType::childCount; i++)
			surfelsNodes<VecType, DataType>(outTree.getRoot(i), tree.constGetRoot(i), subs[i], tree, leafCache);

		outTree.simplify();
	}

	/*template<class V, class T1, class T2, class Ext, class Con>
	static void
	extrudeSimple(NTree<V, T2> &outTree, const NTree<V, T1>& toExtrude, const Ext& extruder)
	{
		std::vector<std::pair<V, T1>> points=NTreeHelpers::getPoints(toExtrude);
		for(unsigned int i=0; i<points.size(); i++)
		{
			std::pair<Con, T2> conParms=extruder.fn(points[i].second);
			MoveCon<V, Con> mover(points[i].first, conParms.first);
			NTree<V, T2> created(mover, conParms.second);
			NTree<V, T2> temp;
			booleanOp<OpUnion<V, T2>, V, T2, T2, T2>(temp, outTree, created);
			outTree=temp;
			outTree.simplify();
		}
		outTree.lower();
	}*/

	template<class V, class T2, class Con>
	static void
	extrudeNodes(typename NTree<V, T2>::Node &outNode,
					const Area<V> &area,
					const Con& constructor,
					T2 userData)
	{
		//change return depending on original type
		switch(outNode.getType())
		{
		case Nil:
			//we can just set what we want here
			switch(constructor.fn(area.toBox()))
			{
			case Nil:
				return;
			case Solid:
				outNode=typename NTree<V, T2>::Node(userData);
				return;
			default:
				if(area.expo == 0)
					return;
				NTree<V, T2>::scanNNode(outNode, area, userData, constructor);
				break;
			}
			return;
		case Solid:
			return;//already solid, nothing to extrude here
		case Both:
			switch(constructor.fn(area.toBox()))
			{
			case Nil://cannot be the case here
				return;
			case Solid:
				outNode=typename NTree<V, T2>::Node(userData);
				return;
			default:
				//recurse
				if(area.expo == 0)
				{
					outNode=typename NTree<V, T2>::Node();
					return;
				}
				Area<V> subAreas[V::childCount];
				area.subAreas(subAreas);
				for (unsigned int i = 0; i < V::childCount; i++)
					extrudeNodes(outNode.getSubNode(i), subAreas[i], constructor, userData);
				//in-place simplify
				outNode.simplify(false);
				break;
			}
			break;
		}
	}

	//in-place
	/*template<class V, class T1, class T2, class Ext, class Con>
	static void
	extrude(NTree<V, T2> &outTree, const NTree<V, T1>& toExtrude, const Ext& extruder)
	{
		std::vector<std::pair<V, T1>> points=NTreeHelpers::getPoints(toExtrude);
		printf("Extruding: ");
		for(unsigned int i=0; i<points.size(); i++)
		{
			std::pair<Con, T2> conParms=extruder.fn(points[i].second);
			Con constr = conParms.first;
			MoveCon<V, Con> mover(points[i].first, constr);

			//raise tree to appropriate level
			outTree.raise(mover.getSize());

			Area<V> subs[V::childCount];
			outTree.subAreas(subs);
			for(unsigned int j=0; j<V::childCount; j++)
				extrudeNodes(outTree.getRoot(j), subs[j], mover, conParms.second);
			
			if((i+1)*50/points.size() != i*50/points.size())
				putchar('.');
		}
		printf("\n");
	}

	//in-place
	template<class V, class T1, class T2, class Ext>
	static void
	extrude(NTree<V, T2> &outTree, const NTree<V, T1>& toExtrude, const Ext& extruder)
	{
		std::vector<std::pair<V, T1>> points=NTreeHelpers::getPoints(toExtrude);

		for(unsigned int i=0; i<points.size(); i++)
		{
			extruder.extrude(outTree, points[i].first, points[i].second);
		}
	}*/

	template<class V, class T>
	class SphereExtrusion
	{
	public:
		SphereExtrusion(float fRadius) : m_fRadius(fRadius) {}
		std::pair<SphereCon<V>, T> fn(T t) const
		{
			return std::make_pair(SphereCon<V>(m_fRadius), t);
		}
	private:
		float m_fRadius;
	};

	template<class V, class T>
	static void
	inset(NTree<V, T> &outTree, const NTree<V, T>& toRound, float fRadius)
	{
		/* ORIGINAL CODE
		//printf("insetting ...\n");
		NTree<V, T> roundable(toRound);
		NTree<V, T> surf;
		//printf("extracting surfels...\n");
		surfels(surf, toRound);
		//printf("simplifying...\n");
		surf.simplify();
		SphereThickenCon<V, T> stc(surf, fRadius);
		//printf("thickening surface ...\n");
		NTree<V, T> thickSurf(stc, 0);
		//printf("boolean op: difference input, thick surface...\n");
		booleanOp<OpDifference<V, T, T, T>, V, T, T, T>(outTree, roundable, thickSurf);
		outTree.lower();
		*/
		//printf("insetting ...\n");

		if(fRadius < 1.0f)
			fRadius = 1.0f;

		NTree<V, T> inverted(toRound);
		//invert tree, so that the boundary grows inward
		NTreeHelpers::invertVoxels<V, T>(inverted);
		//set grow flag to false, so we do'nt thicken the rim of the block
		SphereThickenCon<V, T> stc(inverted, fRadius, false);
		NTree<V, T> thickSurf(stc, 0);
		//subtract thickened surface from original object
		NTree<V, T> roundable(toRound);
		booleanOp<OpDifference<V, T>, V, T, T, T>(outTree, roundable, thickSurf);
		outTree.lower();
	}

	template<class V, class T>
	static void
	offset(NTree<V, T> &outTree, const NTree<V, T>& toRound, float fRadius)
	{
		if(fRadius < 1.0f)
			fRadius = 1.0f;
		//NTree<V, T> roundable(toRound);
		//printf("offsetting ...\n");
		SphereThickenCon<V, T> stc(toRound, fRadius);
		//printf("thickening object ...\n");
		//NTree<V, T> thick(stc, 0);
		//printf("copying to output...\n");
		//this isn't exactly useful...
		outTree.construct(stc, 0);
		//booleanOp<OpUnion<V, T, T, T>, V, T, T, T>(outTree, roundable, thick);
		outTree.lower();
	}

	template<class V, class T>
	static void
	roundConcave(NTree<V, T> &outTree, const NTree<V, T>& toRound, float fRadius)
	{
		if(fRadius<2.0f)
		{
			outTree=toRound;
			return;
		}
		//printf("rounding concave edges...\n");
		NTree<V, T> thickened;
		//printf("offsetting geometry...\n");
		offset(thickened, toRound, fRadius);
		//printf("simplifying...\n");
		thickened.simplify();
		//printf("insetting geometry...\n");
		inset(outTree, thickened, fRadius-0.5f);
}

	template<class V, class T>
	static void
	roundConvex(NTree<V, T> &outTree, const NTree<V, T>& toRound, float fRadius)
	{
		if(fRadius<2.0f)
		{
			outTree=toRound;
			return;
		}
		//printf("rounding convex edges...\n");
		NTree<V, T> insetGeom;
		//printf("insetting geometry...\n");
		inset(insetGeom, toRound, fRadius-0.5f);
		//printf("writing output\n");
		//printf("simplifying...\n");
		insetGeom.simplify();
		//printf("offsetting geometry...\n");
		offset(outTree, insetGeom, fRadius);
	}
};
